package source;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class Matrix {

    /**
     * 有效的数独
     * <p>
     * 请你判断一个 9 x 9 的数独是否有效。
     * 只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
     * <p>
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     *
     * @param board 待判断数独
     * @return 是否符合数组特性
     */
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] lines = new int[9][9];
        int[][][] boxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (sudoku(board, j, i, rows[i], rows)) return false;

                if (sudoku(board, i, j, lines[i], lines)) return false;

                if (board[i][j] != '.' && boxes[i / 3][j / 3][Integer.parseInt(String.valueOf(board[i][j])) - 1] != 1) {
                    boxes[i / 3][j / 3][Integer.parseInt(String.valueOf(board[i][j])) - 1] = 1;
                } else if (board[i][j] != '.' && boxes[i / 3][j / 3][Integer.parseInt(String.valueOf(board[i][j])) - 1] == 1) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean sudoku(char[][] board, int i, int j, int[] line, int[][] lines) {
        if (board[j][i] != '.' && line[Integer.parseInt(String.valueOf(board[j][i])) - 1] != 1) {
            line[Integer.parseInt(String.valueOf(board[j][i])) - 1] = 1;
        } else return board[j][i] != '.' && line[Integer.parseInt(String.valueOf(board[j][i])) - 1] == 1;
        return false;
    }

    /**
     * 给定一个 n × n 的二维矩阵 matrix 表示一个图像。
     * 请你将图像顺时针旋转 90 度。
     * <p>
     * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。
     * 请不要 使用另一个矩阵来旋转图像。
     *
     * @param matrix 原始矩阵
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int tmp;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = tmp;
            }
        }
    }

    /**
     * 矩阵置零
     * <p>
     * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。
     * 请使用 原地 算法。
     *
     * @param matrix m * n 矩阵
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int first = matrix[0][0];
        boolean firstRow = true, firstLine = true; // 第一行没有 0
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                firstRow = false;  // 第一行有 0
                break;
            }
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstLine = false;  // 第一列有 0
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < n; i++) {
            if (matrix[0][i] == 0) {
                for (int j = 1; j < m; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (!firstRow) {
            for (int i = 0; i < n; i++)
                matrix[0][i] = 0;
        }
        if (!firstLine) {
            for (int i = 0; i < m; i++)
                matrix[i][0] = 0;
        }
    }

    /**
     * 生命游戏
     * <p>
     * 根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
     * <p>
     * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：
     * 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。
     * <p>
     * 每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
     * <p>
     * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
     * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
     * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
     * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
     * 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是 同时 发生的。
     * 给你 m x n 网格面板 board 的当前状态，返回下一个状态。
     * <p>
     * 给定当前 board 的状态，更新 board 到下一个状态。
     *
     * @param board 初始状态数组
     */
    public void gameOfLife(int[][] board) {
        // 0 死
        // 1 活
        // 2 死 --> 活
        // 3 活 --> 死
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = change(board, i, j);
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 2)
                    board[i][j] = 1;
                else if (board[i][j] == 3) {
                    board[i][j] = 0;
                }
            }
        }

    }

    private int change(int[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        int live = 0;
        for (int x = i - 1; x <= i + 1; x++) {
            if (x >= 0 && x < m) {
                for (int y = j - 1; y <= j + 1; y++) {
                    if (x == i && y == j)
                        continue;
                    if (y >= 0 && y < n) {
                        if (board[x][y] == 1 || board[x][y] == 3) {
                            live++;
                        }
                    }
                }
            }
        }

        if (board[i][j] == 1) {
            if (live < 2 || live > 3)
                return 3;
            else return 1;
        } else {
            if (live == 3)
                return 2;
            return 0;
        }
    }


    /**
     * 螺旋矩阵
     *
     * @param matrix m 行 n 列的矩阵 matrix
     * @return 按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        // int i = 0;
        // int j = 0;

        int up = 0, down = m - 1, left = -1, right = n - 1;

        List<Integer> list = new ArrayList<>();
        int num = m * n;
        while (num > 0) {
            for (int i = ++left; i <= right && num > 0; i++) {
                list.add(matrix[up][i]);
                num--;
            }
            for (int i = ++up; i <= down && num > 0; i++) {
                list.add(matrix[i][right]);
                num--;
            }
            for (int i = --right; i >= left && num > 0; i--) {
                list.add(matrix[down][i]);
                num--;
            }
            for (int i = --down; i >= up && num > 0; i--) {
                list.add(matrix[i][left]);
                num--;
            }
        }
        return list;
    }


    @Test
    public void testSpiral() {
        int[][] arr = {{1}, {49}};
        System.out.println(spiralOrder(arr));
    }


}
